home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1999 March / EnigmA AMIGA RUN 35 (1999)(G.R. Edizioni)(IT)[!][issue 1999-03].iso / earcd / -archivi / -recent2 / amhelios.lha / AmHelios / oct_quan.h < prev    next >
C/C++ Source or Header  |  1997-07-13  |  7KB  |  268 lines
  1. ////////////////////////////////////////////////////////////
  2. //
  3. //  OCT_QUAN.H - Octree Color Quantization Class Include
  4. //               File
  5. //
  6. //  Version:    1.03A
  7. //
  8. //  History:    94/08/23 - Version 1.00A release.
  9. //              94/11/11 - Version 1.00B release.
  10. //              94/11/27 - Converted to MS-Windows
  11. //                         environment.
  12. //              94/12/16 - Version 1.01A release.
  13. //              94/12/19 - Added GetNumColors function.
  14. //              95/02/05 - Version 1.02A release.
  15. //              95/02/11 - Simplified TestBit function.
  16. //                       - Modified O_MaxDepth to account
  17. //                         for 6-bit color display adapters.
  18. //                       - Modified FindChild to eliminate
  19. //                         dependence on O_MaxDepth.
  20. //              95/07/21 - Version 1.02B release.
  21. //              96/02/14 - Version 1.02C release.
  22. //              96/04/01 - Version 1.03A release.
  23. //
  24. //  Compilers:  Microsoft Visual C/C++ Professional V1.5
  25. //              Borland C++ Version 4.5
  26. //
  27. //  Author:     Ian Ashdown, P.Eng.
  28. //              byHeart Software Limited
  29. //              620 Ballantree Road
  30. //              West Vancouver, B.C.
  31. //              Canada V7S 1W3
  32. //              Tel. (604) 922-6148
  33. //              Fax. (604) 987-7621
  34. //
  35. //  Copyright 1994-1996 byHeart Software Limited
  36. //
  37. //  The following source code has been derived from:
  38. //
  39. //    Ashdown, I. 1994. Radiosity: A Programmer's
  40. //    Perspective. New York, NY: John Wiley & Sons.
  41. //
  42. //  It may be freely copied, redistributed, and/or modified
  43. //  for personal use ONLY, as long as the copyright notice
  44. //  is included with all source code files.
  45. //
  46. ////////////////////////////////////////////////////////////
  47.  
  48. #ifndef _OCT_QUAN_H
  49. #define _OCT_QUAN_H
  50.  
  51. #include "color.h"
  52.  
  53. // Maximum octree reduction level
  54. //
  55. // NOTE: Most 256-color display adapters are only capable
  56. //       of generating 262,144 distinct colors (64 colors
  57. //       per 6-bit color channel). Since this effectively
  58. //       truncates an 8-bit color value to 6 bits, the
  59. //       octree depth need not exceed five levels below
  60. //       the root node.
  61.  
  62. static const int O_MaxDepth = 5;
  63.  
  64. // Maximum number of palette colors
  65. static const int O_MaxColors = 256;
  66.  
  67. class OctNode           // Octree node
  68. {
  69.   private:
  70.     int level;          // Node level
  71.     BOOL leaf_flag;     // Leaf flag
  72.     BOOL mark_flag;     // Marked flag
  73.     DWORD count;        // Pixel count
  74.     struct
  75.     {
  76.       DWORD red;
  77.       DWORD green;
  78.       DWORD blue;
  79.     }
  80.     sum;                // Summed color value
  81.     int index;          // Color palette index
  82.     int children;       // Number of child nodes
  83.     OctNode *pchild[8]; // Children node pointers
  84.     OctNode *pnext;     // Next reducible node pointer
  85.     OctNode *pprev;     // Previous reducible node pointer
  86.  
  87.     int TestBit(BYTE val, int index)
  88.     { return ((val >> index) & 0x01); }
  89.  
  90.   public:
  91.     OctNode( int node_level, BOOL leaf )
  92.     {
  93.       int i;    // Loop index
  94.  
  95.       level = node_level;
  96.       leaf_flag = leaf;
  97.       mark_flag = FALSE;
  98.       count = 0L;
  99.       index = 0;
  100.       children = 0;
  101.       sum.red = sum.green = sum.blue = 0L;
  102.  
  103.       for (i = 0; i < 8; i++)
  104.         pchild[i] = NULL;
  105.  
  106.       pnext = pprev = NULL;
  107.     };
  108.  
  109.     BOOL IsLeaf() { return leaf_flag; }
  110.     BOOL IsMark() { return mark_flag; }
  111.  
  112.     DWORD GetCount() { return count; }
  113.  
  114.     ColorRGB GetColor()
  115.     {
  116.       ColorRGB temp;    // Temporary color
  117.  
  118.       temp.SetRed((BYTE) (sum.red / count));
  119.       temp.SetGreen((BYTE) (sum.green / count));
  120.       temp.SetBlue((BYTE) (sum.blue / count));
  121.  
  122.       return temp;
  123.     }
  124.  
  125.     int GetIndex() { return index; }
  126.     int GetLevel() { return level; }
  127.  
  128.     // Determine child node according to color
  129.     int FindChild( ColorRGB &c )
  130.     {
  131.       int index;    // Child node pointer index
  132.  
  133.       // Determine child node pointer index
  134.       index = TestBit(c.GetRed(), (7 - level)) << 2 |
  135.           TestBit(c.GetGreen(), (7 - level)) << 1 |
  136.           TestBit(c.GetBlue(), (7 - level));
  137.  
  138.       return index;
  139.     }
  140.  
  141.     OctNode *GetChild( int i ) { return pchild[i]; }
  142.     OctNode *GetNext() { return pnext; }
  143.     OctNode *GetPrev() { return pprev; }
  144.     int GetNumChild() { return children; }
  145.  
  146.     // Add RGB color to node
  147.     void AddColor( ColorRGB &c )
  148.     {
  149.       sum.red += (DWORD) c.GetRed();
  150.       sum.green += (DWORD) c.GetGreen();
  151.       sum.blue += (DWORD) c.GetBlue();
  152.  
  153.       count++;
  154.     }
  155.  
  156.     void DecNumChild() { children--; }
  157.     void IncNumChild() { children++; }
  158.     void SetChild( int i, OctNode *pc ) { pchild[i] = pc; }
  159.     void SetIndex( int i ) { index = i; }
  160.     void SetLeaf( BOOL flag ) { leaf_flag = flag; }
  161.     void SetMark( BOOL flag ) { mark_flag = flag; }
  162.     void SetNext( OctNode *pn ) { pnext = pn; }
  163.     void SetPrev( OctNode *pn ) { pprev = pn; }
  164. };
  165.  
  166. class OctQuant          // Octree color quantization
  167. {
  168.   private:
  169.     int leaf_level;     // Leaf level
  170.     int num_leaf;       // Number of leaf nodes
  171.  
  172.     // Reducible node list pointers
  173.     OctNode *prnl[O_MaxDepth + 1];
  174.  
  175.     OctNode *proot;     // Octree root node pointer
  176.  
  177.     BOOL BuildTree();
  178.     BOOL InsertNode( OctNode *, ColorRGB & );
  179.  
  180.     OctNode *MakeNode( int level )
  181.     {
  182.       BOOL leaf;    // Leaf node flag
  183.  
  184.       leaf = (BOOL)((level >= leaf_level) ? TRUE : FALSE);
  185.  
  186.       if (leaf == TRUE)
  187.         num_leaf++;
  188.  
  189.       return new OctNode(level, leaf );
  190.     }
  191.  
  192.     OctNode *GetReducible();
  193.  
  194.     // Quantize color
  195.     int QuantizeColor( OctNode *pn, ColorRGB &c )
  196.     {
  197.       int c_index;      // Child node pointer index
  198.  
  199.       if ((pn->IsLeaf() == TRUE) || pn->GetLevel() ==
  200.           leaf_level)
  201.         return pn->GetIndex();
  202.       else
  203.       {
  204.         c_index = pn->FindChild(c);
  205.  
  206.         return QuantizeColor(pn->GetChild(c_index), c);
  207.       }
  208.     }
  209.  
  210.     void DeleteNode( OctNode * );
  211.     void DeleteTree();
  212.     void FillPalette( OctNode *, int * );
  213.  
  214.     // Add node to reducible list
  215.     void MakeReducible( OctNode *pn )
  216.     {
  217.       int level;        // Node level
  218.       OctNode *phead;   // List head node
  219.  
  220.       level = pn->GetLevel();
  221.       phead = prnl[level];
  222.       pn->SetNext(phead);
  223.       if (phead != NULL)
  224.         phead->SetPrev(pn);
  225.       prnl[level] = pn;
  226.  
  227.       pn->SetMark(TRUE);
  228.     }
  229.  
  230.     void MapColors();
  231.     void ReduceTree();
  232.  
  233.   protected:
  234.     int height;         // Bitmap height
  235.     int width;          // Bitmap width
  236.     int max_colors;     // Maximum number of colors
  237.     int num_colors;     // Number of palette entries
  238.  
  239.     // Bitmap color palette
  240.     ColorRGB palette[O_MaxColors];
  241.  
  242.     virtual void GetPixel( int, int, ColorRGB * ) = 0;
  243.     virtual void SetPalPixel( int, int, BYTE & ) = 0;
  244.  
  245.   public:
  246.     OctQuant()
  247.     {
  248.       int i;    // Loop index
  249.  
  250.       width = height = 0;
  251.       num_leaf = 0;
  252.       num_colors = 0;
  253.       leaf_level = O_MaxDepth + 1;
  254.  
  255.       // Clear the reducible node list pointers
  256.       for (i = 0; i < leaf_level; i++)
  257.         prnl[i] = NULL;
  258.  
  259.       proot = NULL;
  260.     }
  261.  
  262.     BOOL Quantize();
  263.     int GetNumColors() { return num_colors; }
  264. };
  265.  
  266. #endif
  267.  
  268.